package com.nlp.trie.ternary;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.StringTokenizer;

/**
 * 三叉Trie树
 * @author dwjf321
 *
 */
public class TernarySearchTrie {
	
	public TSTNode rootNode;
	
	private static TernarySearchTrie dic = null;
	
	public TernarySearchTrie(String path) {
		try {
			FileReader reader = new FileReader(path);
			BufferedReader read = new BufferedReader(reader);
			String temstr = "";
			while((temstr = read.readLine()) != null) {
				TSTNode node = null;
				StringTokenizer st = new StringTokenizer(temstr, "\t");
				String key = st.nextToken();
				if (rootNode == null) {
					rootNode = new TSTNode(key.charAt(0));
				}
				int charIndex = 0;
				TSTNode currentNode = rootNode;
				while(true) {
					if (currentNode == null) {
						break;
					}
					int compa = key.charAt(charIndex)-currentNode.spliter;
					if (compa == 0) {
						charIndex++;
						if (charIndex == key.length()) {
							node = currentNode;
							break;
						}
						currentNode = currentNode.eqNode;
					}else if (compa < 0) {
						currentNode = currentNode.loNode;
					}else if (compa > 0) {
						currentNode = currentNode.hiNode;
					}
				}
				if (node == null) {
					currentNode = createTSTNode(key);
					currentNode.data = key;
				}
			}
			read.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
		
	}

	/**
	 * 创建一个节点
	 * @param key
	 * @return
	 */
	private TSTNode createTSTNode(String key) {
		if (key == null) {
			throw new NullPointerException("key为空");
		}
		int charIndex = 0;
		TSTNode currentNode = rootNode;
		if (rootNode == null) {
			rootNode = new TSTNode(key.charAt(0));
		}
		while (true) {
			int compa = key.charAt(charIndex) - currentNode.spliter;
			if (compa == 0) {
				charIndex++;
				if (charIndex == key.length()) {
					return currentNode;
				}
				if (currentNode.eqNode == null) {
					currentNode.eqNode = new TSTNode(key.charAt(charIndex));
				}
				currentNode = currentNode.eqNode;
			}else if (compa < 0) {
				if (currentNode.loNode == null) {
					currentNode.loNode = new TSTNode(key.charAt(charIndex));
				}
				currentNode = currentNode.loNode;
			}else if (compa > 0) {
				if (currentNode.hiNode == null) {
					currentNode.hiNode = new TSTNode(key.charAt(charIndex));
				}
				currentNode = currentNode.hiNode;
			}
			
			
		}
	}

	/**
	 * 最大长度匹配
	 * @param key
	 * @param offset
	 * @return
	 */
	public String matchLong(String key, int offset) {
		String ret = null;
		if (key == null || rootNode == null || "".equals(key)) {
			return ret;
		}
		TSTNode currentNode = rootNode;
		int charIndex = offset;
		while(true) {
			if (currentNode == null) {
				return ret;
			}
			int compat = key.charAt(charIndex) - currentNode.spliter;
			if (compat == 0) {
				charIndex++;
				if (currentNode.data != null) {
					ret = currentNode.data;//候选最长匹配词
				}
				if (charIndex == key.length()) {
					return ret;//已经匹配完
				}
				currentNode = currentNode.eqNode;
			}else if (compat < 0) {
				currentNode = currentNode.loNode;
			}else if (compat > 0) {
				currentNode = currentNode.hiNode;
			}
		}
	}
	public static TernarySearchTrie getInstance() {
		if (dic == null) {
			String path = "dic.txt";
			dic = new TernarySearchTrie(path);
		}
		
		return dic;
	}
	



	public static void main(String[] args) {
		TernarySearchTrie dic = new TernarySearchTrie("E:\\search\\nlp\\trie\\src\\main\\resources\\TernarySearchTrie");
		String key = "活动中心大学生";
		int offset = 0;
		String ret = dic.matchLong(key,offset);
		System.out.println(key+" match:"+ret);
	}
	
	public final class TSTNode{
		public String data;
		
		protected TSTNode loNode;
		protected TSTNode eqNode;
		protected TSTNode hiNode;
		
		public char spliter;
		
		public TSTNode(char key) {
			this.spliter = key;
		}
		@Override
		public String toString() {
			String data = "data是"+this.data+"\t spliter 是"+spliter;
			return data;
		}
	}

}
